package tree

//给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
//如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的
//输入：p = [1,2,3], q = [1,2,3]  输出：true
//输入：p = [1,2], q = [1,null,2] 输出：false
//输入：p = [1,2,1], q = [1,1,2]  输出：false

//方法1：利用深度优先搜索
func IsSameTreeDFS(p *Node, q *Node) bool {
	if p == nil && q == nil {
		return true
	}
	if p == nil || q == nil {
		return false
	}
	if p.Val != q.Val {
		return false
	}
	//若相同，再分别判断两个二叉树的左子树是否相同以及右子树是否相同
	return IsSameTreeDFS(p.Left, q.Left) && IsSameTreeDFS(p.Right, q.Right)
}

func IsSameTreeBFS(p *Node, q *Node) bool {
	if p == nil && q == nil {
		return true
	}
	if p == nil || q == nil {
		return false
	}
	queue1, queue2 := []*Node{p}, []*Node{q}
	for len(queue1) > 0 && len(queue2) > 0 {
		node1, node2 := queue1[0], queue2[0]
		queue1, queue2 = queue1[1:], queue2[1:]
		if node1.Val != node2.Val {
			return false
		}
		left1, right1 := node1.Left, node1.Right
		left2, right2 := node2.Left, node2.Right
		//如果只有一个节点的左子节点为空
		if (left1 == nil && left2 != nil) || (left1 != nil && left2 == nil) {
			return false
		}
		//如果只有一个节点的右子节点为空
		if (right1 == nil && right2 != nil) || (right1 != nil && right2 == nil) {
			return false
		}

		//将两个节点的非空子节点分别加入两个队列
		if left1 != nil {
			queue1 = append(queue1, left1)
		}
		if right1 != nil {
			queue1 = append(queue1, right1)
		}
		if left2 != nil {
			queue2 = append(queue2, left2)
		}
		if right2 != nil {
			queue2 = append(queue2, right2)
		}
	}
	return len(queue1) == 0 && len(queue2) == 0
}
